#include <bits/stdc++.h>

using namespace std;



struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool helper(TreeNode *A,TreeNode *B){
        if(A==nullptr){
            return (B?false:true);
        } 
        if(B==nullptr) return true;
        if(A->val!=B->val) return false;
        

        return helper(A->left,B->left) && helper(A->right,B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(B==nullptr) return false;
        if(A==nullptr) return false;
        if(A->val==B->val && helper(A,B) ){
            return true;
        } 
        if(isSubStructure(A->left,B)) return true;
        if(isSubStructure(A->right,B)) return true;
        return false;
    }
};
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}
void prin(TreeNode* root){
    if(root==nullptr) return;
    queue<TreeNode *> s;
    s.push(root);
    while(!s.empty()){
        TreeNode *p=s.front();s.pop();
        if(p->left) s.push(p->left);
        if(p->right) s.push(p->right);
        cout << p->val << " ";
    }cout <<endl;

}

int main(){
    vector<int> A={1,2,3};
    vector<int> B={3};
    TreeNode *pa=gou(A);
    TreeNode *pb=gou(B);
    Solution s;
    cout << s.isSubStructure(pa,pb) <<endl;


    return 0;
}